package tree;

import node.Node;

import java.util.*;

/**
 * @author Yakiv Tymoshenko
 * @since 14.10.12
 */
public class TreeScanner {

    private Tree tree;
    private int treeHeight;
    private LinkedHashSet<Node> visitedNodes;
    private Set<Object> keySet;
    private boolean treeScanned;

    public TreeScanner(Tree tree) {
        this.tree = tree;
        treeScanned = false;
        int size = tree.getNodes().size();
        visitedNodes = new LinkedHashSet<Node>(size);
        keySet = new LinkedHashSet<Object>(size);
    }

    public String printKeys() {
        visitNodes();
        StringBuilder stringBuilder = new StringBuilder();
        for (Object key : keySet) {
            stringBuilder.append(key);
            stringBuilder.append(" ");
        }
        stringBuilder.append("\n");
        return stringBuilder.toString();
    }

    public String printVisitedNodes() {
        visitNodes();
        StringBuilder stringBuilder = new StringBuilder();
        for (Node node : visitedNodes) {
            stringBuilder.append(node.getIndex());
            stringBuilder.append(" ");
        }
        stringBuilder.append("\n");
        return stringBuilder.toString();
    }

    public void visitNodes() {
        if (!treeScanned) {
            visitNode(tree.getRoot());
            calcTreeHeight();
            addKeys();
            initLevelNodesMap();
            treeScanned = true;
        }
    }

    private void visitNode(Node node) {
        visitedNodes.add(node);
        visitLeftChild(node);
        visitRightChild(node);
    }

    private void visitLeftChild(Node node) {
        Node left = node.getLeft();
        if (left != null) {
            visitNode(left);
        }
    }

    private void visitRightChild(Node node) {
        Node right = node.getRight();
        if (right != null) {
            visitNode(right);
        }
    }

    private void addKeys() {
        for (Node node : visitedNodes) {
            keySet.add(node.getKey());
        }
    }

    private void initLevelNodesMap() {
        Map<Integer, Set<Node>> levelNodesMap = new HashMap<Integer, Set<Node>>(treeHeight);
        int distanceFromParent;
        for (Node node : visitedNodes) {
            distanceFromParent = distanceFromParent(node) + 1;
            Set<Node> value = levelNodesMap.get(distanceFromParent);
            Set<Node> newValue = value == null ? new HashSet<Node>() : value;
            newValue.add(node);
            levelNodesMap.put(distanceFromParent, newValue);
        }
    }

    private void calcTreeHeight() {
        treeHeight = maxDistanceFromChildToRoot(childlessNodes()) + 1;
    }

    private Set<Node> childlessNodes() {
        Set<Node> result = new LinkedHashSet<Node>();
        for (Node node : visitedNodes) {
            if (node.getLeft() == null && node.getRight() == null) {
                result.add(node);
            }
        }
        return result;
    }

    private int maxDistanceFromChildToRoot(Set<Node> childlessNodes) {
        List<Node> childlessNodesList = new ArrayList<Node>(childlessNodes);
        Node node = childlessNodesList.get(0);
        int result = distanceFromParent(node);
        for (int i = 1; i < childlessNodesList.size(); i++) {
            int nextDistance = distanceFromParent(childlessNodesList.get(i));
            if (result < nextDistance) {
                result = nextDistance;
            }
        }
        return result;
    }

    private int distanceFromParent(Node child) {
        int result = 0;
        Node parent = child.getParent();
        while (parent != null) {
            result++;
            parent = parent.getParent();
        }
        return result;
    }

    public LinkedHashSet<Node> getVisitedNodes() {
        return new LinkedHashSet<Node>(visitedNodes);
    }

    public Set<Object> getKeySet() {
        return new LinkedHashSet<Object>(keySet);
    }

    public Tree getTree() {
        return tree;
    }

    public int getTreeHeight() {
        return treeHeight;
    }
}
